//
//  20_有效的括号.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/1/24.
//

import UIKit

class Solution {
    static func QA() {
        let item = Solution()
        let state = item.isValid1("}")
        print("*********", state)
    }
    
    func isValid(_ s: String) -> Bool {
        if s.count == 0 {
            return false
        }
        let stack = Stack<Character>()
        for char in s {
            if char == "{" || char == "[" || char == "(" {
                stack.push(char)
            } else {
                if char == "}" {
                    let left = stack.top()
                    if left == "{" {
                        stack.pop()
                        continue
                    } else {
                        return false
                    }
                }
                if char == "]" {
                    let left = stack.top()
                    if left == "[" {
                        stack.pop()
                        continue
                    } else {
                        return false
                    }
                }
                if char == ")" {
                    let left = stack.top()
                    if left == "(" {
                        stack.pop()
                        continue
                    } else {
                        return false
                    }
                }
            }
        }
        return stack.isEmpty()
    }
    
    // 精简版（栈）
    func isValid1(_ s: String) -> Bool {
        if s.count == 0 {
            return false
        }
        let stack = Stack<Character>()
        for char in s {
            if char == "{" || char == "[" || char == "(" {
                stack.push(char)
            } else {
                if stack.isEmpty() {
                    return false
                }
                let left = stack.pop()
                if left == "{" && char != "}" {
                    return false
                }
                if left == "[" && char != "]" {
                    return false
                }
                if left == "(" && char != ")" {
                    return false
                }
                
            }
        }
        return stack.isEmpty()
    }
}
